package com.zhugang.week13.stack;

import java.util.Stack;

/**
 * @program algorithms
 * @description: SortedStack
 * @author: chanzhugang
 * @create: 2022/11/03 15:12
 */
public class SortedStack {

    /**
     * 面试题03.05 栈排序
     * https://leetcode.cn/problems/sort-of-stacks-lcci/
     * 使最小的元素位于栈顶
     */

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tempStack = new Stack<>();

    public SortedStack() {

    }

    /**
     * 画个图理解，入栈直接倒腾完比 出栈倒腾好
     *
     * @param val
     */
    public void push(int val) {
        // 保持栈的数据从大到小排序: 栈顶元素 < val, 把栈顶元素倒腾到临时栈
        while (!stack.isEmpty() && stack.peek() < val) {
            tempStack.push(stack.pop());
        }

        stack.push(val);
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            // 特殊处理
            return;
        }
        stack.pop();
    }

    public int peek() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}